R. Альфред и Георг

Математики Альфред и Георг играют в игру. Они берут белый клетчатый листок размером n×m клеток. Сначала Альфред раскрашивает некоторые клетки в чёрный цвет, после чего Георг должен снова перекрасить все клетки в белый. Для этого Георг сколько угодно раз проделывает следующую операцию:

Поместить карандаш в левый нижний угол листка (будем считать, что это точка с координатами (0,0)), после чего нарисовать путь в верхний правый угол листка (точку с координатами (n,m)). Путь должен проходить только по границам клеток, кроме того, передвигать карандаш можно только вправо и вверх, то есть из позиции (x,y) карандаш можно передвинуть только в позиции (x+1,y) и (x,y+1), если при этом карандаш не покинет пределов листка.
Перекрасить все клетки листка, расположенные под нарисованным путём, в противоположный цвет (то есть, все белые клетки под путём перекрасить в чёрный цвет, а все чёрные — в белый). После этого нарисованный путь стирается, и (если это необходимо) Георг переходит к следующей операции.
Пока Георг работает, Альфред пытается посчитать в уме, за какое минимальное число операций можно было бы закончить игру, начиная с исходного рисунка. Для самопроверки он попросил вас написать программу, которая бы находила ответ на этот вопрос.

В первой строке записано три целых числа n, m и k (1≤n,m≤500000, 0≤k≤500000) — размеры листка и количество закрашенных клеток соответственно.
Следующие k строк описывают закрашенные клетки. i-я из этих строк содержит два целых числа xi,yi — координаты левого нижнего угла i-й закрашенной клетки в системе координат, описанной выше (0≤xi<n, 0≤yi<m). Гарантируется, что закрашенные клетки не повторяются.

Выведите одно число — минимальное количество операций, нужное, чтобы завершить игру. Если перекрасить всю доску в белый цвет невозможно, выведите −1.

